package com.lry.basic.algorithm.sort;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/9
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,4,2,1};
        new MergeSort().sort(arr);
        for (int i :arr) {
            System.out.print(i+" ");
        }
    }

    public void sort(int[] arr){
        if(null==arr||arr.length==0||arr.length==1)return;
        mergeSort(arr,0,arr.length-1);
    }

    private void mergeSort(int[] arr,int low,int high){
        if(low==high)return;
        int mid = (low+high)/2;
        mergeSort(arr,low,mid);
        mergeSort(arr,mid+1,high);
        merge(arr,low,mid,high);
    }

    /**
     * low~mid 有序  mid+1~high有序  该方法会使low~high有序
     * @param arr 待排序数组
     * @param low
     * @param mid
     * @param high
     */
    private void merge(int[] arr,int low,int mid,int high){
        int []tmp = new int[arr.length];
        int tmpI = low;
        int leftStart = low;
        int rightStart = mid+1;
        //挑小的
        while(leftStart<=mid&&rightStart<=high){
            if(arr[leftStart]<arr[rightStart]){
                tmp[tmpI++] = arr[leftStart++];
            }else{
                tmp[tmpI++] = arr[rightStart++];
            }
        }
        //余下的
        while(leftStart<=mid){
            tmp[tmpI++] = arr[leftStart++];
        }
        //余下的
        while(rightStart<=high){
            tmp[tmpI++] = arr[rightStart++];
        }
        //复制过去
        while(low<=high){
            arr[low] = tmp[low];
            low++;
        }
    }
}
